// Copyright (c) [Year] [name of copyright holder]
// [Software Name] is licensed under Mulan PSL v2.
// You can use this software according to the terms and conditions of the Mulan PSL v2. 
// You may obtain a copy of Mulan PSL v2 at:
//          http://license.coscl.org.cn/MulanPSL2 
// THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.  
// See the Mulan PSL v2 for more details.

/*!
 * \autor captainpeng
 * \date 2019-5-15
 * \version 1.0
 */

#ifndef MY_MEMAVLTREE_HPP
#define MY_MEMAVLTREE_HPP

#include"cassert"
#include"memFunc.hpp"

#define MEMAVL_CHECKNOW(now) assert(((now) < MAX_HEIGHT)? true:!static_cast<bool>("my::memAVLTree::insert 记录树超出限定树的高度"));

#define MEMAVLERR_ALLOCREPEAT() assert(!static_cast<bool>("my::memAVLTree::insert 分配时出现重复地址"));
namespace my{

    class memAVLNode{
	public:
        using funcType = memFreeFunc;
        using valueType = void *;
        using sizeType = size_t;
        using countType = unsigned short;
        using heightType = short;

        valueType mValue;       // 分配内存的地址
        valueType mLast;        // 分配栈中的上一个字符, nullptr 的时候为最后一个了
        sizeType mSize;         // 分配内存地址的大小
        countType mCount;       // 计数器
        funcType mFree;         // 进行 delete 的函数指针

        heightType mHeight;     // 树的高度
        memAVLNode * mLeft;     // 左子树
        memAVLNode * mRight;    // 右子树

        memAVLNode():
            mValue(nullptr),
            mLast(nullptr),
            mSize(0),
            mCount(0),
            mFree(nullptr),
            mHeight(0),
            mLeft(nullptr),
            mRight(nullptr)            
            {}

        memAVLNode(valueType val, valueType last, sizeType size, countType count, memFreeFunc free):
            mValue(val),
            mLast(last),
            mSize(size),
            mCount(count),
            mFree(free),
            mHeight(0),
            mLeft(nullptr),
            mRight(nullptr)
            {}

        ~memAVLNode(){
            // std::cout<<"~memAVLNode: "<<this<<", "<<(mValue)<<std::endl;
            free();
#ifdef MY_ENABLE_DEBUG
            if(mRight != nullptr)
                std::cout<<"memAVLNode "<<(void *)this<<" 析构时， mRight != nullptr"<<std::endl;
            if(mLeft != nullptr)
                std::cout<<"memAVLNode "<<(void *)this<<" 析构时， mLeft != nullptr"<<std::endl;
#endif
            delete mRight;
            delete mLeft;
        }

        inline void free(){
            if(mFree != nullptr) (*mFree)(mValue);
        }

        // 信息交换，树节点不交换
        void swapInfo(memAVLNode & rhs){
            if(this == &rhs) return;

            // 交换内存块地址
            valueType vtmp = mValue;
            mValue = rhs.mValue;
            rhs.mValue = vtmp;

            // 交换大小
            sizeType stmp = mSize;
            mSize = rhs.mSize;
            rhs.mSize = stmp;

            // 交换计数器
            countType ctmp = mCount;
            mCount = rhs.mCount;
            rhs.mCount = ctmp;

            // 交换上一个内存块
            vtmp = mLast;
            mLast = rhs.mLast;
            rhs.mLast = vtmp;

            // 交换释放函数
            funcType ftmp = mFree;
            mFree = rhs.mFree;
            rhs.mFree = ftmp;
        }

        // 信息交换，关于节点的信息的交换
        void swapNodeInfo(memAVLNode & rhs){
            // 交换高度
            heightType htmp = mHeight;
            mHeight = rhs.mHeight;
            rhs.mHeight = htmp;

            // 交换左右子树
            memAVLNode * ttmp = mLeft;
            mLeft = rhs.mLeft;
            rhs.mLeft = ttmp;

            ttmp = mRight;
            mRight = rhs.mRight;
            rhs.mRight = ttmp;
        }

        bool isAt(void * val){
            void * value = static_cast<void *>(static_cast<uint8_t *>(mValue) + mSize);
            // std::cout<<"isAt "<<(val >= mValue && val < value)<<" "<<(void *)value<<" mSize == "<<mSize<<std::endl;
            return val >= mValue && val < value;
        }

        inline void plusCount(){
            ++mCount;
        }
        
        inline void minusCount(){
            if(mCount > 0) --mCount;
        }
	};

    class memAVLTree{
    public:
		using nodeType = memAVLNode;
		using treeType = nodeType *;
        using valueType = typename nodeType::valueType;
        using sizeType = typename nodeType::sizeType;
        using countType = typename nodeType::countType;
        using heightType = typename nodeType::heightType;

        static const int MAX_HEIGHT = 1024;
        static const int MAX_NUM = 1049;

	private:
        treeType mHead;
        treeType mStack[MAX_HEIGHT];
        char mDirec[MAX_HEIGHT];

        static inline heightType Height(treeType node){
            if(node == nullptr) return -1;
            return node->mHeight;
        }
        
        static inline void HeightCal(treeType node){
            if(node == nullptr) return ;
            heightType lh = Height(node->mLeft);
            heightType rh = Height(node->mRight);
            node->mHeight = (lh > rh? lh:rh) + 1;
        }
        
        static treeType SingleRotateWithLeft(treeType k2){
            treeType k1;

            k1 = k2->mLeft;
            k2->mLeft = k1->mRight;
            k1->mRight = k2;

            HeightCal(k1);
            HeightCal(k2);

            return k1;
        }

        static treeType SingleRotateWithRight(treeType k2){
            treeType k1;

            k1 = k2->mRight;
            k2->mRight = k1->mLeft;
            k1->mLeft = k2;

            HeightCal(k1);
            HeightCal(k2);

            return k1;
        }
        
        static treeType DoubleRotateWithLeft(treeType k3){
            k3->mLeft = SingleRotateWithRight(k3->mLeft);
            return SingleRotateWithLeft(k3);
        }

        static treeType DoubleRotateWithRight(treeType k3){
            k3->mRight = SingleRotateWithLeft(k3->mRight);
            return SingleRotateWithRight(k3);
        }

        static void PrintNode(treeType t, int count = 0, char c = 'h'){
            for(int i = 0; i < count; ++i)
                std::cout<<"  ";

            if(t == nullptr){
                std::cout<<"NULL"<<std::endl;
                return ;
            }
            
            std::cout<<"["<<(void *)t<<", "<<t->mHeight<<" : "<<c<<", "<<t->mValue<<", "<<t->mSize<<", "<<t->mLast<<", "<<t->mCount<<"]\n";
            PrintNode(t->mLeft, count+1, 'l');
            PrintNode(t->mRight, count+1, 'r');
        }

        static treeType EraseFindMin(treeType node, treeType * S, char * D, int & now){
            if(node == nullptr) return nullptr;
            while(node->mLeft != nullptr){
                S[++now] = node;
                D[now] = 'l';
                node = node->mLeft;
            }
            return node;
        }

    public:
        memAVLTree():mHead(nullptr){}

        ~memAVLTree(){
            free();
        }

        void * insert(valueType last, size_t size, size_t typesize, countType count, memAllocFunc fnAlloc, memFreeFunc fnFree){
            int now = -1;
            treeType node = new nodeType((*fnAlloc)(size), last, size*typesize, count, fnFree);
			treeType cur = mHead;

            // 1. 先查找，栈记录着查找的路径，找到合适位置后再进行旋转平衡操作
            while(true){
                if(cur == nullptr){
                    cur = node;
                    break;
                }

				// assert(((++now) < MAX_HEIGHT)?true:!static_cast<bool>("my::memAVLTree::insert 记录树超出限定树的高度"));
                MEMAVL_CHECKNOW(++now);

				mStack[now] = cur;
				if(node->mValue < cur->mValue){
                    mDirec[now] = 'l';
					// std::cout<<"["<<now<<"] left"<<std::endl;
                    cur = cur->mLeft;
                }else if(node->mValue > cur->mValue){
                    mDirec[now] = 'r';
					// std::cout<<"["<<now<<"] right"<<std::endl;
                    cur = cur->mRight;
                }else{
                    // 出现重复 new 的，报错，程序停止运行
                    // assert(!static_cast<bool>("my::memAVLTree::insert 分配时出现重复地址"));
                    std::cerr<<"## 地址重复 "<<node->mValue<<", "<<cur->mValue<<" ##"<<std::endl;
                    MEMAVLERR_ALLOCREPEAT();
                    delete node;
                    return nullptr;
                }
            }

            // 2. 旋转平衡，此时 cur 是平衡当前子树头节点的
            for(;now >= 0; --now){
                if(mDirec[now] == 'l'){
                    mStack[now]->mLeft = cur;
                }else if(mDirec[now] == 'r'){
                    mStack[now]->mRight = cur;
                }

				cur = mStack[now];
				if((Height(cur->mLeft) - Height(cur->mRight)) == 2)
					if(mDirec[now+1] == 'l')
						cur = SingleRotateWithLeft(cur);
					else
						cur = DoubleRotateWithLeft(cur);
				else if((Height(cur->mRight) - Height(cur->mLeft)) == 2)
					if(mDirec[now+1] == 'r')
						cur = SingleRotateWithRight(cur);
                    else
						cur = DoubleRotateWithRight(cur);

                HeightCal(cur);
            }

			mHead = cur;
            return node->mValue;
        }

        treeType find(void * val){
            treeType cur = mHead;
            while(true){
                if(cur == nullptr) return nullptr;

                if(val < cur->mValue)
                    cur = cur->mLeft;
                else if(val > cur->mValue)
                    cur = cur->mRight;
                else
                    return cur;
            }
        }

        static treeType findMin(treeType cur){
            while(cur->mLeft != nullptr){
                cur = cur->mLeft;
            }
			
            return cur;
        }

        static treeType findMax(treeType cur){
            while(cur->mRight != nullptr){
                cur = cur->mRight;
            }
			
            return cur;
        }

		void free(){
			// int now = 0;
            // mStack[now] = mHead;
			// treeType cur = mStack[now];
			// while(cur != nullptr){
			// 	if(cur->mLeft != nullptr){
			// 		mStack[++now] = cur->mLeft;
            //         cur->mLeft = nullptr;
			// 	}else if(cur->mRight != nullptr){
			// 		mStack[++now] = cur->mRight;
            //         cur->mRight = nullptr;
			// 	}else{
            //         delete cur;
            //         --now;
			// 	}
            //     cur = (now >= 0)? mStack[now]:nullptr;
			// }
			//mHead = nullptr;

            // 2020-4-8
            // 因为删掉一个内存块有可能因为析构函数连带删掉更多的内存块，所以上述的算法失效。
            // 考虑到一般只有程序结束之后才会调用该函数，调用次数较少，所以采用最愚蠢的办法清空内存管理器。

            while(mHead != nullptr)
                erase(mHead->mValue);
		}

        void erase(void * val){
            if(mHead == nullptr) return;

#ifdef MY_ENABLE_DEBUG
            std::cout<<"------ my::memAVLTree::erase, pt = "<<val<<" begin -------"<<std::endl;
            print();
#endif
            int now = -1;

            treeType cur = mHead;
            treeType del = nullptr;
            // 1. 先查找，栈记录着查找的路径，找到合适位置后再进行旋转平衡操作
            while(true){
				if(val < cur->mValue){
                    mStack[++now] = cur;
                    mDirec[now] = 'l';
                    cur = cur->mLeft;
                }else if(val > cur->mValue){
                    mStack[++now] = cur;
                    mDirec[now] = 'r';
                    cur = cur->mRight;
                }else if(cur->mLeft != nullptr && cur->mRight != nullptr){
                    // 拥有两个子节点的时候
                    mStack[++now] = cur;
                    mDirec[now] = 'r';
                    int curnow = now;

                    // 找到 cur->mRight 的最小值
                    // 最小值 del 一定是没有左子树的，也是最后要删除的节点
                    del = cur->mRight;
                    while(del->mLeft != nullptr){
                        mStack[++now] = del;
                        mDirec[now] = 'l';
                        del = del->mLeft;
                    }

                    // 删除节点或删除内存块时候请保证二叉树的完整性
                    // 此时二叉树在修改中，并不完整

                    // 交换内存块信息，一定要交换，别再这里删除内存块
                    // cur->swapInfo(*del);

                    // 交换节点信息，不交换值的信息
                    // 交换之后
                    // cur->节点的信息 == 原 del 的，但 cur->值的信息 == 原 cur 的
                    // del->节点的信息 == 原 cur 的，但 del->值的信息 == 原 del 的
                    // 那么 cur 将变成要被删掉的，而 del 变为要保存到 curnow 的
                    cur->swapNodeInfo(*del);
                    
                    mStack[curnow] = del;
                    del = cur;

                    // 不管 del->mRight 有没有子树，cur 都要保存下来
                    cur = del->mRight;
                    del->mRight = nullptr;

                    break;
                }else{
                    // 拥有一个或者零个子节点的时候
                    // 当前节点就是我们将要删除的节点
                    del = cur;
                    if(cur->mLeft == nullptr){
                        cur = cur->mRight;
                        del->mRight = nullptr;
                    }else{
                        cur = cur->mLeft;
                        del->mLeft = nullptr;
                    }

                    break;
                }
            }

            // 2. 旋转平衡，此时 cur 是平衡当前子树头节点的
            for(;now >= 0; --now){
                if(mDirec[now] == 'l'){
                    mStack[now]->mLeft = cur;
                }else if(mDirec[now] == 'r'){
                    mStack[now]->mRight = cur;
                }

				cur = mStack[now];
				if(Height(cur->mLeft) - Height(cur->mRight) == 2){
                    // std::cout<<"erase "<<(void *)cur<<", "<<Height(cur->mLeft)<<", "<<Height(cur->mRight)<<std::endl;
					if(cur->mLeft->mLeft != nullptr)
						cur = SingleRotateWithLeft(cur);
					else
						cur = DoubleRotateWithLeft(cur);
                }else if(Height(cur->mRight) - Height(cur->mLeft) == 2)
					if(cur->mRight->mRight != nullptr)
						cur = SingleRotateWithRight(cur);
					else
						cur = DoubleRotateWithRight(cur);

                HeightCal(cur);
            }

            mHead = cur;
            delete del;

#ifdef MY_ENABLE_DEBUG
            print();
            std::cout<<"----- my::memAVLTree::erase, node = "<<del<<" end ------"<<std::endl;
#endif
        }

        // 遍历整棵树，请输入 lambda 表达式
        template<typename Call>
        void each(const Call & c){
            treeType cur = mHead;
            int now = -1;
            bool back_flag = false;
            while(cur != nullptr){
                MEMAVL_CHECKNOW(now);
                if(!back_flag){
                    mStack[++now] = cur;
                    mDirec[now] = 'l';
                    if(cur->mLeft != nullptr){
                        cur = cur->mLeft;
                        continue;
                    }
                }
                
                if(mDirec[now] == 'l'){
                    mDirec[now] = 'r';
                    if(cur->mRight != nullptr){
                        cur = cur->mRight;
                        back_flag = false;
                        continue;
                    }
                }

                if(mDirec[now] == 'r'){
                    if(!c(cur)) return ;
                    cur = now > 0? mStack[--now]:nullptr;
                    back_flag = true;
                }
            }
        }

		void print(){
            PrintNode(mHead);
        }
    };
}

#endif
